Bereichstheorie
Die Bereichstheorie ist ein Zweig der Mathematik, der spezielle Arten von Halbordnungen, gemeinhin als Bereiche oder Domänen bekannt, untersucht. Sie kann als ein Teilgebiet der Ordnungstheorie betrachtet werden. Die Bereichstheorie beinhaltet wichtige Anwendungen in der Informatik, die in der Funktionensemantik (denotationellen Semantik) insbesondere für funktionale Programmiersprachen verwendet werden.Introduction to Domain Theory School of Computer Science, University of Nottingham - abgerufen am 2. Februar 2013 Sie formalisiert die intuitive Vorstellungen von Annäherung und Konvergenz in einer sehr allgemeinen Weise und unterhält enge Beziehungen zur Topologie. Ein alternativer wichtiger Ansatz zur Funktionensemantik sind die metrischen Räume. Motivation und Formulierung Die primäre Motivation für das Studium der Domänen, die durch Dana Scott in den späten 1960er Jahren initiiert wurde, war die Suche nach der Funktionensemantik des Lambda-Kalküls. Der Lambda-Kalkül ist eine formale Sprache zur Untersuchung von Funktionen. Diese formale Sprache beschreibt Funktionsdefinitionen, das Definieren formaler Parameter sowie das Auswerten und Einsetzen aktueller Parameter. In einer rein syntaktischen Weise kann man von einfachen Funktionen auf Funktionen die andere Funktionen übernehmen und ihre Eingabeargumente schließen. Mit syntaktischen Transformationen aus diesem Formalismus, erhält man sogenannte Fixpunktkombinatoren (der bekannteste ist der Y-Kombinator). Um eine solche Funktionensemantik zu formulieren, könnte man zunächst versuchen, ein Modell für den Lambda-Kalkül, in dem eine echte (gesamte) Funktion mit jedem Lambda-Term assoziiert ist, zu konstruieren. Ein solches Modell würde eine rein syntaktische Verbindung zwischen dem Lambda-Kalkül und dem Kalkül als Darstellungsmittel zur Manipulation konkreter mathematischer Funktionen formalisieren. Der kombinatorische Kalkül ist ein solches Modell. Jedoch sind die Elemente des kombinatorischen Kalküls Funktionen aus Funktionen zu Funktionen. Sie können also nicht wirkliche Funktionen sein, sondern lediglich Teilfunktionen. Berechnung und Modellierung Die Berechnung zur Lösung dieser Schwierigkeit durch Formalisierung einer Vorstellung von "teilweisen" oder "unvollständigen" Informationen kommt zu einem Ergebnis, das unter folgender Berücksichtigung modelliert wird: Für jede Domäne einer Berechnung (zb. natürliche Zahlen), wird ein zusätzliches Element, das eine undefinierte Ausgabe darstellt herangezogen. Die Folge ist das Ergebnis einer Berechnung, die niemals endet. Außerdem wird der Bereich der Berechnung mit einer Ordnungsrelation versehen, wobei das "undefiniert Ergebnis" das kleinste Element darstellt. Um den wichtigen Schritt eins Modells für den Lambda Kalkül zu finden, ist es notwendig, die Funktionen einer solchen Halbordnung mit garantierten Mindestfixpunkten zu berücksichtigen. Die Menge dieser Funktionen, zusammen mit einer geeigneten Reihenfolge, ist wiederum eine "Domäne" im Sinne der Bereichstheorie. Durch die Beschränkung auf eine Teilmenge aller verfügbaren Funktionen ist es möglich, Domänen die ihre eigenen Funktionsleerzeichen beinhalten zu erhalten. Diese Domänen erhalten also eine Funktion, die auf sie selbst angewendet werden kann. Neben diesen Eigenschaften ermöglicht die Bereichstheorie auch eine ansprechende, intuitive Interpretation. Wie bereits erwähnt, werden die Domänen der Berechnung immer teilweise angeordnet. Diese Reihenfolge stellt eine Hierarchie von Informationen oder Wissen dar. Je höher ein Element innerhalb der Ordnung ist, desto spezifischer ist es und desto mehr Informationen enthält es. In der Hierarchie unten angesiedelte Elemente repräsentieren unvollständiges Wissen oder unvollständige Zwischenergebnisse. Die Berechnung wird in weiterer Folge durch Anlegen monotoner Funktionen auf Elemente der Domäne wiederholt, um ein Ergebnis zu verfeinern. Das Erreichen eines festen Punktes bedeutet die Endbearbeitung einer solchen Berechnung. Übersicht der formalen Definitionen Dieser Abschnitt beinhaltet die zentralen Konzepte und Definitionen der Bereichstheorie. Führende Sätze als konvergierende Daten Die Bereichstheorie befasst sich mit Halbordnungen um die Berechnung einer Domäne zu modellieren. Das Ziel besteht darin, die Bestandteile bzw. Elemente einer solchen Reihenfolge wie Informationsteile oder Teilergebnisse einer Berechnung so zu interpretieren, das die in der höheren Ebene angesiedelten Informationen mit den darunterliegenden Elementen einen konsistenten Weg aufweisen. Der dadurch bedingte, logische Rückschluss ergibt, dass Domänen nicht oft ein größeres Element darstellen, da dies bedeuten würde, dass es ein solches Element sämtliche Informationen aller anderen Elemente beinhaltet, was wiederum eine eher uninteressante Situation darstellt. Eine wichtige Rolle bei dieser Theorie spielt die gerichtete Teilmenge einer Domäne. Das bedeutet eine nicht leere Untergruppe der betreffenden Reihenfolge in der jeweils zwei Elemente eine Obergrenze aufweisen, die für sich ein Element dieser Teilmenge darstellen. Im Hinblick auf die Intuition zu Domänen bedeutet dies, dass die oben angeführten Teile von Informationen innerhalb der höherwertigen Teilmenge konsequent durch ein anderes Element in ebendieser Teilmenge erweitert werden. Diese Interpretation kann mit dem Begriff einer konvergenten Folge verglichen werden, wobei jedes Element spezifischer ist, als das Vorhergehende. In der Alternative, der Theorie der metrischen Räume, stehen Sequenzen in vielerlei Hinsicht analog zu den Sequenzen der Bereichstheorie. Von der Grundidee der teilweise angegebenen Ergebnisse als Vertreter unvollständigen Wissens, wird eine andere Eigenschaft abgeleitet, die Existenz eines kleinsten Elements. Ein solches Element enthält keine Informationen, dient aber als „Ort“, an dem die meisten Berechnungen beginnen, bzw. als Ausgangspunkt einer Berechnung. Domänenfunktionen Domänen beinhalten Funktionen wie Eingänge von Berechnungen und Ausgänge von selbigen. Man geht aufgrund dieser Feststellung davon aus, dass der Ausgang einer Funktion mehr Informationen enthält, wenn der Informationsgehalt des Eingangs ebenso erweitert wird. Formal bedeutet dies, dass eine Funktion monoton sein soll. Eine vollständige Halbordnung (CPO) ist eine Halbordnung mit einem kleinsten Element und der Eigenschaft, dass jede Teilmenge, die eine aufsteigende Kette bildet, ein „Oberstes“ (Supremum) besitzt. Das Supremum muss dabei nicht in der Teilmenge selbst liegen. Zu beachten ist auch, dass unter Berücksichtigung der gerichteten Sätze von zwei Elementen, eine solche Funktion ebenso monoton zu sein hat. Diese Eigenschaften führen zu der Vorstellung einer Scott-stetigen Funktion. Approximation und Endlichkeit Die Bereichstheorie stellt einen rein qualitativen Ansatz zur Modellierung einer Struktur von Informationen und Zuständen dar. Aufgrund dieses Ansatzes wird angenommen, dass etwas mehr Informationen enthält, aber die Menge an zusätzlichen Informationen nicht angegeben ist. Dennoch stellen bestimmte Situationen eine Notwendigkeit dar, um über Elemente, die in einem gewissen Sinne einen viel einfacheren oder viel unvollständigeren Zustand von Informationen beinhalten, zu sprechen. Um eine solche Beziehung zu modellieren, muss man die induzierte strenge Ordnung (<) einer Domäne mit der Ordnung (≤) betrachten. Approximationsordnung Eine aufwendigere Methode der Modellierung führt zur sogenannten Approximationsordnung. Das Element x'' approximiert ''y, in Zeichen x \ll y , wenn für jede gerichtete Menge D mit y \sqsubseteq \sup D ein Element d \in D existiert mit x \sqsubseteq d . Aus x \ll y folgt x \sqsubseteq y , da \{y\} eine gerichtete Menge ist. Das Supremum der Kette \{0\}, \{0, 1\}, \{0, 1, 2\}, \ldots ist die Menge aller natürlichen Zahlen N''' und zeigt, dass keine unendliche Menge '''N approximieren kann. Grundlagen von Domänen Im Allgemeinen beschränkt man sich auf eine bestimmte Teilmenge von Elementen die als immer ausreichend für alle anderen Elemente als kleinste obere Schranke anzunehmen ist. Folglich definiert man die Basis der Korrelationsungleichung (Posets) P''' als eine Teilmenge '''B an P''' derart, dass diese für '''X bis P''', die Menge der Elemente in '''B, die weit unter X''' stehen einen gerichteten Satz mit dem Supremum '''X enthält. Die Poset P ist eine kontinuierliche Korrelationsungleichung wenn sie über eine eigene Basis verfügt. Solch ein Poset wird als algebraisch angesehen. Aus der Sicht der Funktionensemantik werden algebraische Posets besonders gut aufgenommen, da sie die Angleichung aller Elemente, auch wenn eine Beschränkung besteht, ermöglicht. Jedoch ist nicht jedes endliche Element "endlich" im klassischen Sinne, weswegen es erforderlich ist, diese Endlich-Elemente in einer unzähligen Reihe darzustellen. In manchen Fällen jedoch dienen diese Endlichen-Elemente als Basis für zählbare Posets. In diesem Fall spricht man von einem ω-kontinuierlichen Poset. Dementsprechend erhält man eine Ordnung die ω-algebraisch ist. Besondere Arten von Domänen Eine einfache Art einer Domäne wird als elementare oder flache Domäne bezeichnet. Diese besteht aus einem Satz von unvergleichbaren Elementen, die insgesamt mit einem einzigen "unteren" Element betrachtet kleiner ist, als alle anderen Elemente. Eine weitere Art von Domänen sind kontinuierliche Posets und algebraische Posets. Bei gegebener Vollständigkeit erhält man kontinuierliche Gitter und algebraische Gitter. Die historischen Klassen von Posets, die sogenannten Scott Domains, waren die ersten Strukturen in der Bereichstheorie, die untersucht wurden. Weitere Klassen von Domänen sind SFP-Domänen und L-Domänen. Alle diese Klassen von Domänen können, unter Verwendung ihrer jeweiligen Funktionen, wieder in verschiedene Kategorien unterteilt werden. In monotone, Scott-kontinuierliche oder sogar spezialisierte Morphismen (Kategorientheorie). Letztendlich ist zu beachten, dass der Begriff Domäne selbst nicht genau definiert ist und somit nur als Abkürzung bzw. formale Definition verwendet wird. Siehe auch * Scott-Topologie * Kategorientheorie Weblinks * Fachgruppe für Theoretische Informatik - Universität Siegen – deutsch * Topological Domain Theory-Übersicht - englisch * Domain Theory (1994) by Samson Abramsky - englisch * Domain Theory - Corrected and expanded version (PDF, 1.06 MB) Einzelnachweise Kategorie:Teilgebiet der Mathematik